n=1000;
like=[|115,749|
733,436|
47,586|
823,667|
799,102|
348,202|
611,651|
774,187|
513,656|
40,99|
714,981|
48,826|
419,198|
334,624|
953,219|
876,536|
275,709|
356,741|
610,318|
803,773|
842,152|
309,224|
243,591|
523,859|
347,42|
440,317|
60,145|
527,907|
157,152|
735,502|
247,707|
206,779|
414,690|
406,872|
566,295|
841,650|
853,308|
614,668|
586,554|
10,768|
669,420|
618,25|
955,829|
430,111|
734,799|
476,246|
3,920|
784,12|
427,145|
138,965|
655,570|
238,911|
673,917|
74,338|
111,470|
209,866|
942,506|
686,464|
281,175|
27,134|
550,871|
757,494|
305,979|
306,726|
897,975|
829,783|
946,911|
540,966|
312,358|
606,790|
245,789|
337,712|
267,494|
54,585|
712,592|
232,356|
737,290|
813,484|
620,743|
693,113|
675,714|
763,135|
825,931|
718,305|
526,505|
212,715|
881,818|
316,234|
400,835|
871,301|
875,244|
263,679|
525,139|
641,218|
974,109|
200,133|
486,899|
488,967|
10,698|
533,951|
330,983|
750,5|
264,619|
863,529|
172,470|
880,164|
521,449|
772,988|
95,804|
582,694|
44,55|
505,884|
642,80|
456,716|
393,1|
154,691|
590,300|
359,585|
292,342|
541,392|
647,341|
526,128|
886,689|
973,234|
200,196|
832,947|
935,934|
122,599|
538,875|
710,477|
483,691|
386,802|
96,692|
769,60|
169,82|
259,971|
255,945|
610,50|
93,985|
275,708|
223,475|
503,154|
632,850|
367,674|
27,49|
351,565|
509,519|
487,703|
884,510|
791,982|
304,239|
29,21|
820,780|
142,116|
625,320|
365,910|
29,988|
543,541|
882,306|
605,879|
367,891|
552,961|
921,896|
251,106|
955,885|
860,658|
649,637|
446,387|
369,135|
591,373|
652,450|
105,785|
839,507|
389,342|
990,59|
253,517|
834,375|
854,394|
492,335|
425,431|
649,902|
250,902|
515,795|
775,456|
976,642|
680,936|
8,282|
413,469|
355,587|
826,883|
621,806|
635,524|
787,701|
771,265|
291,425|
125,321|
584,679|
13,410|
337,703|
96,125|
677,942|
384,6|
416,270|
862,242|
771,209|
535,32|
390,678|
746,265|
205,56|
511,946|
284,286|
909,86|
474,731|
461,833|
850,555|
453,259|
903,847|
980,94|
952,15|
547,271|
767,685|
539,282|
141,750|
432,22|
886,450|
1000,810|
645,511|
435,601|
280,302|
504,751|
376,479|
76,680|
662,377|
88,124|
670,381|
285,423|
974,364|
52,442|
917,151|
384,493|
874,464|
204,747|
848,23|
91,639|
71,254|
395,46|
908,31|
452,861|
468,440|
182,551|
164,264|
460,693|
664,176|
868,245|
137,311|
581,855|
657,527|
941,665|
216,136|
976,278|
583,627|
553,977|
92,979|
103,251|
208,194|
534,362|
851,73|
697,912|
430,498|
756,203|
540,220|
518,538|
992,554|
330,843|
17,140|
523,928|
593,549|
522,260|
724,638|
229,720|
597,59|
222,187|
943,960|
211,618|
473,236|
211,840|
838,528|
922,978|
687,315|
811,77|
346,195|
119,621|
821,663|
689,312|
35,500|
737,401|
507,333|
788,869|
480,823|
117,595|
559,90|
229,454|
391,424|
797,151|
63,84|
159,64|
960,329|
493,37|
22,700|
608,774|
801,255|
69,294|
394,748|
931,905|
289,729|
478,88|
925,26|
796,19|
383,992|
155,730|
640,196|
758,475|
802,831|
853,784|
952,542|
536,696|
332,606|
897,530|
307,340|
274,101|
615,340|
327,858|
297,360|
14,909|
630,179|
808,726|
72,199|
54,363|
999,438|
331,329|
121,399|
119,174|
426,985|
555,906|
654,409|
921,291|
25,939|
434,6|
572,652|
433,654|
993,146|
708,857|
385,918|
896,482|
715,189|
76,18|
704,398|
395,69|
382,118|
795,333|
561,927|
266,628|
746,338|
790,237|
497,156|
451,614|
144,161|
810,782|
659,169|
970,743|
439,391|
966,674|
793,170|
721,723|
177,814|
231,839|
987,233|
434,716|
707,932|
653,735|
852,235|
359,566|
633,319|
240,202|
353,604|
845,132|
168,819|
742,568|
174,780|
418,207|
303,371|
120,588|
438,115|
178,313|
246,358|
991,948|
575,499|
357,441|
341,401|
89,907|
399,296|
542,817|
609,414|
472,490|
496,844|
34,643|
545,738|
558,647|
345,510|
615,198|
516,709|
776,569|
188,459|
403,33|
732,792|
203,682|
537,700|
688,390|
13,958|
41,849|
935,702|
747,460|
236,657|
466,303|
195,180|
343,580|
49,491|
671,579|
569,489|
44,269|
180,604|
599,224|
436,350|
348,378|
228,738|
2,433|
692,900|
393,339|
984,371|
26,249|
584,398|
495,238|
865,877|
740,711|
957,704|
448,168|
454,633|
467,446|
962,107|
225,171|
366,989|
248,753|
673,216|
447,302|
883,962|
114,184|
623,595|
598,532|
867,413|
422,252|
214,660|
565,766|
760,752|
58,241|
560,910|
754,424|
448,567|
889,249|
965,188|
55,105|
664,667|
804,404|
285,581|
213,922|
141,322|
571,46|
130,972|
316,819|
788,231|
299,999|
678,864|
354,662|
827,131|
563,78|
767,600|
898,97|
616,148|
984,98|
490,429|
404,489|
905,427|
949,179|
240,308|
62,73|
572,442|
499,405|
365,933|
817,269|
397,496|
295,878|
857,713|
711,30|
142,646|
230,890|
112,85|
57,736|
173,297|
702,564|
800,147|
409,149|
210,227|
550,989|
9,830|
964,656|
858,183|
411,694|
176,699|
686,272|
147,1000|
742,838|
107,658|
587,278|
276,24|
822,192|
888,93|
85,122|
28,257|
832,287|
778,104|
717,328|
608,957|
930,458|
856,100|
699,266|
794,206|
16,326|
417,938|
129,272|
222,620|
271,68|
158,120|
402,325|
556,158|
828,959|
407,990|
765,892|
220,898|
622,571|
725,277|
512,61|
856,250|
562,162|
619,262|
39,273|
344,215|
543,557|
912,556|
666,408|
301,869|
583,465|
835,361|
963,552|
842,484|
508,659|
462,146|
35,382|
467,807|
812,388|
412,429|
51,969|
476,548|
349,495|
670,967|
768,785|
397,721|
836,636|
638,706|
631,781|
428,954|
426,846|
256,473|
110,894|
261,560|
441,197|
74,118|
39,3|
522,189|
671,392|
890,698|
872,117|
170,23|
75,672|
824,277|
801,958|
300,457|
879,948|
281,732|
458,940|
128,432|
644,485|
228,624|
630,923|
710,639|
385,431|
160,681|
327,70|
996,685|
531,310|
640,403|
138,19|
865,7|
870,682|
626,926|
38,366|
410,331|
918,487|
901,892|
284,42|
553,103|
79,539|
191,292|
816,548|
457,776|
601,14|
155,803|
665,613|
964,261|
941,362|
873,781|
602,335|
578,634|
887,143|
447,383|
631,870|
192,758|
893,576|
167,846|
279,577|
603,244|
609,321|
733,94|
185,113|
406,827|
908,600|
749,227|
503,916|
408,121|
928,996|
181,167|
36,891|
7,751|
349,171|
380,881|
350,345|
51,663|
9,514|
257,423|
166,521|
564,369|
681,461|
901,798|
233,482|
655,293|
471,253|
626,258|
806,558|
471,4|
763,38|
41,683|
573,235|
428,588|
766,592|
53,453|
372,144|
924,81|
991,968|
895,201|
481,207|
92,197|
186,232|
660,605|
612,416|
778,669|
719,755|
607,221|
58,518|
852,289|
418,757|
294,123|
822,33|
131,116|
133,437|
80,252|
110,516|
812,815|
833,326|
268,824|
589,99|
534,517|
309,417|
193,900|
508,421|
199,148|
357,445|
944,888|
894,577|
379,31|
140,352|
17,411|
130,603|
444,502|
75,72|
963,501|
81,11|
86,355|
378,114|
752,530|
84,828|
684,866|
280,924|
374,575|
937,728|
791,374|
279,855|
549,831|
64,336|
914,814|
997,722|
843,315|
320,893|
213,754|
415,597|
641,2|
45,944|
380,30|
506,764|
296,77|
435,407|
796,968|
444,947|
779,18|
388,520|
370,79|
971,926|
756,919|
363,208|
242,422|
313,934|
1,645|
223,102|
230,651|
717,463|
987,452|
466,731|
914,684|
270,745|
62,688|
322,635|
887,903|
764,463|
954,927|
998,915|
82,668|
760,736|
546,818|
462,672|
221,485|
574,40|
134,916|
995,787|
194,205|
108,841|
20,970|
310,8|
998,184|
623,412|
993,939|
529,683|
32,741|
153,389|
629,578|
830,368|
66,889|
48,324|
574,172|
809,956|
193,770|
479,298|
994,71|
364,70|
150,723|
844,415|
807,373|
825,535|
360,183|
739,318|
808,304|
661,877|
45,5|
509,851|
594,311|
132,323|
625,20|
472,109|
895,874|
666,191|
567,793|
797,336|
786,981|
368,226|
951,290|
695,568|
837,78|
727,375|
695,920|
622,973|
402,498|
765,87|
478,387|
880,153|
864,293|
690,524|
4,299|
697,593|
794,83|
12,190|
483,643|
544,718|
66,43|
513,782|
323,725|
528,126|
696,214|
837,177|
561,89|
576,961|
813,834|
520,287|
376,173|
982,286|
772,36|
21,563|
274,729|
405,792|
867,386|
580,637|
217,885|
933,243|
420,986|
143,215|
800,267|
381,687|
324,37|
178,949|
724,256|
533,551|
501,352|
515,332|
24,972|
969,166|
248,878|
204,936|
104,937|
821,481|
443,611|
719,56|
459,845|
254,913|
559,298|
634,612|
90,61|
590,34|
629,899|
241,805|
129,91|
16,915|
443,798|
861,500|
596,160|
820,106|
653,87|
159,919|
190,455|
112,149|
165,847|
123,225|
759,632|
705,525|
468,783|
504,589|
650,161|
546,617|
636,730|
706,582|
677,805|
354,163|
328,65|
547,486|
873,97|
437,701|
617,661|
182,181|
217,759|
930,995|
314,491|
344,956|
400,28|
644,247|
334,212|
465,156|
52,67|
268,557|
925,868|
727,755|
762,876|
769,646|
53,239|
353,616|
745,882|
815,47|
346,163|
288,474|
602,997|
720,675|
913,317|
744,613|
361,761|
648,276|
983,932|
532,904|
314,83|
929,379|
848,497|
748,127|
127,421|
186,862|
722,863|
994,537|
777,347|
978,598|
258,628|
57,201|
986,283|
705,734|
137,950|
210,67|
740,126|
396,596|
492,854|
953,945|
811,100|
325,219|
15,950|
761,579|
165,43|
906,786|
531,445|
419,594|
977,544|
307,283|
836,162|
455,449|
713,562|
627,514|
469,50|
68,372|
573,98|
739,676|
860,570|
773,370|
136,744|
859,477|
816,124|
95,237|
65,980|
260,185|
959,262|
288,940|
63,263|
218,975|
11,809|
840,150|
101,929|
488,439|
139,343|
943,849|
377,753|
108,157|
451,512|
175,545|
396,676|
319,273|
351,777|
789,938|
904,770|
607,648|
923,728|
762,775|
339,480|
226,519|];